package com.cuz.series.linklist;

/***
 * https://leetcode.cn/problems/reverse-linked-list-ii/
 */
public class 链表2反转指定位置之间的单链表 {

    public static void main(String[] args) {
        ListNode node = ListNode.of1(1, 2, 3, 4, 5);
        ListNode node1 = reverseBetween2(node, 2, 4);
        node1.print();
    }

    public static ListNode reverseBetween2(ListNode head, int left, int right) {
        ListNode preHead = new ListNode();
        preHead.next = head;
        //left位置对应的节点
        ListNode l = head;
        //left的前置节点
        ListNode lp = preHead;
        //走到left位置对应的节点
        for (int i = 0; i < left - 1; i++) {
            l = l.next;
            lp = lp.next;
        }
        //
        ListNode pre = lp;
        //前进
        lp = lp.next;
        l = l.next;


        //翻转
        for (int i = 0; i < right - left; i++) {
            //l节点断开连接
            lp.next = l.next;
            //l的下一个节点指向pre的下一个节点，翻转
            l.next = pre.next;
            //pre 和l连接起来
            pre.next = l;
            //移动
            l = lp.next;
        }

        return preHead.next;
    }

    public static ListNode reverseBetween1(ListNode head, int left, int right) {
        if (head == null || head.next == null || left == right) {
            return head;
        }

        Result result = find(head, left, right);

        result.lp.next = null;
        result.r.next = null;
        ListNode[] nodes = reverseList1(result.l);
        ListNode rHead = nodes[0];
        ListNode rTail = nodes[1];
        result.lp.next = rHead;
        rTail.next = result.rn;

        return result.isFromHead ? result.r : head;
    }


    public static ListNode[] reverseList1(ListNode head) {

        //哑节点，
        ListNode preHead = new ListNode();
        preHead.next = head;
        //当前遍历到的节点
        ListNode cur = head.next;
        //当前遍历到节点的前置节点
        ListNode curPre = head;

        while (cur != null) {

            //断开cur的指针
            curPre.next = cur.next;

            //cur 插入到preHead中间。
            cur.next = preHead.next;
            preHead.next = cur;

            //继续
            cur = curPre.next;
        }

        return new ListNode[]{preHead.next, head};
    }

    static class Result {
        //left 位置的节点
        ListNode l;
        //right 位置的节点
        ListNode r;
        //l位置节点的前一个节点
        ListNode lp;
        //r位置的下一个节点
        ListNode rn;
        boolean isFromHead;

        public Result(ListNode l, ListNode r, ListNode lp, ListNode rn) {
            this.l = l;
            this.r = r;
            this.lp = lp;
            this.rn = rn;
        }
    }

    public static Result find(ListNode head, int left, int right) {
        //pre-check忽略
        ListNode loop = head;
        ListNode l = null;
        ListNode lp = null;
        for (int i = 1; i < left; i++) {
            if (i == left - 1) {
                lp = loop;
                l = loop.next;
                break;
            }
            loop = loop.next;
        }
        ListNode r = null;
        ListNode rn = null;
        loop = head;
        for (int i = 1; i < right; i++) {
            if (i == right - 1) {
                r = loop.next;
                rn = loop.next.next;
                break;
            }
            loop = loop.next;
        }
        if (lp == null) {
            lp = new ListNode();
            lp.next = head;
            l = head;
            Result r1 = new Result(l, r, lp, rn);
            r1.isFromHead = true;
            return r1;
        }

        return new Result(l, r, lp, rn);
    }
}
